package jianzhioffer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/21 15:53
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 */
public class offer_39_数组中出现次数超过一半的数字 {

    public static void main(String[] args) {
        int[] nums = {6, 6, 6, 7, 7};
        System.out.println(majorityElement(nums));
    }

//    自己做的先排序，然后找出现最多的元素，时间很长，不推荐
    public static int majorityElement1(int[] nums) {
        if (nums.length==1) return nums[0];
        for (int i=0; i<nums.length; i++){
            for (int j=i+1; j<nums.length; j++){
                if (nums[j]<nums[i]){
                    int tem = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tem;
                }
            }
        }
        int count=1;
        for (int i=0; i<nums.length-1; i++){
            if (nums[i]==nums[i+1])
                count ++;
            else count = 1;
            if (count>nums.length/2)
                return nums[i];
        }
        return -1;
    }

//    利用哈希表做，效率依然不是很高
    public static int majorityElement2(int[] nums) {
        if (nums.length==1) return nums[0];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++){
            if (!map.containsKey(nums[i])) map.put(nums[i],1);
            else map.put(nums[i], map.get(nums[i])+1);
        }
        int res = 0, min = 0;
        for (Map.Entry<Integer, Integer> entry:map.entrySet()){
            Integer value = entry.getValue();
            if (value>min){
                min = value;
                res = entry.getKey();
            }
        }
        return res;
    }

//    摩尔投票
    public static int majorityElement(int[] nums) {
//        x代表众数，count代表投票
        int x = 0, count = 0;
        for (int i=0; i<nums.length; i++){
            if (count == 0) x = nums[i];
            if (x==nums[i]) count ++;
            else count --;
        }
        return x;
    }
}
